package algorithm.middle;

import java.util.Arrays;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-04-24 15:23
 * @Description: 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 *
 * 题目数据保证答案符合 32 位整数范围。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-iv
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CombinationSum4 {

    public int[] dp;
    public int[] nums;
    //记忆化递归
    public int combinationSum4(int[] nums, int target) {
        dp = new int[target+1];
        Arrays.sort(nums);
        this.nums = nums;
        dp[0] = 1;
        fun(target);
        return dp[target];
    }

    //循环数组中的每一个数字 itemCount = dp[target - nums[i]] item相加和

    /**
     * nums = [1,2,3], target = 4
     *  item = 1 dp[3] = 4
     *  item = 2 dp[2] = 2
     *  item = 3 dp[1] = 1
     */
    public void fun(int target){
        for (int i=0;i<nums.length;i++){
            if (nums[i]>target) break;
            int index = target - nums[i];
            if (dp[index]==0) fun(index);
            dp[target] +=dp[index];
        }
    }

    //动态规划 即计算1~target的每个数字的组合个数
    public static int combinationSum42(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        Arrays.sort(nums);
        for (int i=1;i<=target;i++){
            //此处的i为每个数
            for (int x:nums){
                //比i小的数组元素逐一dp相加
                if (i>=x){
                    dp[i] += dp[i-x];
                }
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        combinationSum42(new int[]{1,2,3},4);
    }
}
